package com.hyb.algorithm.data.struct.backtrack;

import com.alibaba.fastjson.JSONObject;

import java.util.ArrayList;
import java.util.List;

/**
 * 131. 分割回文串
 * https://leetcode.cn/problems/palindrome-partitioning/
 *
 * @author: ybhu
 * @create: 2023/12/28 16:13
 */
public class Partition1 {


    private int[][] f;

    public static void main(String[] args) {

        // substring  endIndex=3   len=endIndex-startIndex=3-0=3
        //System.out.println( "aab".substring(0,3));
        List<List<String>>  res1=  new Partition1().partition("aab");

        System.out.println(JSONObject.toJSON(res1));


    }

    private List<List<String>> res;

    public List<List<String>> partition(String s) {

        int n = s.length();
        f = new int[n][n];

        res = new ArrayList<List<String>>();

        List<String> list = new ArrayList<String>();
        backTrack(s, 0, list);

        return res;
    }


    public void backTrack(String s, int indexStart, List<String> list) {
        //递归、回溯终止条件
        if (indexStart == s.length()) {

            System.out.println(JSONObject.toJSON(list));

            res.add(new ArrayList<>(list) );

            return;
        }

        for (int i = indexStart; i < s.length(); i++) {
            if (isPalindrome(s, indexStart, i) == 1) {
                //// substring 要多加1  比如 i+1   表示的就是[indexStart,i]
                list.add(s.substring(indexStart, i + 1));
                backTrack(s, i + 1, list);
                list.remove(list.size() - 1);
            }

        }
    }


    //记忆化搜索中，f[i][j] = 0 表示未搜索，1 表示是回文串，-1 表示不是回文串
    private int isPalindrome(String s, int i, int j) {

        if (f[i][j] != 0) {
            return f[i][j];
        }

        if (i >= j) {
            f[i][j] = 1;
        } else if (s.charAt(i) == s.charAt(j)) {
            //双指针 移动 i 后移， j 前移
            f[i][j] = isPalindrome(s, i + 1, j - 1);
        } else {
            f[i][j] = -1;
        }


        return f[i][j];
    }
}
